{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Balance a Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #tree #depth-first-search #binary-search-tree #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #树 #深度优先搜索 #二叉搜索树 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: balanceBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将二叉搜索树变平衡"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉搜索树，请你返回一棵&nbsp;<strong>平衡后</strong>&nbsp;的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。</p>\n",
    "\n",
    "<p>如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 <code>1</code> ，我们就称这棵二叉搜索树是&nbsp;<strong>平衡的</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/10/balance1-tree.jpg\" style=\"height: 319px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,null,3,null,4,null,null]\n",
    "<strong>输出：</strong>[2,1,3,null,null,null,4]\n",
    "<strong>解释：</strong>这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/10/balanced2-tree.jpg\" style=\"height: 145px; width: 224px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [2,1,3]\n",
    "<strong>输出:</strong> [2,1,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树节点的数目在&nbsp;<code>[1, 10<sup>4</sup>]</code>&nbsp;范围内。</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [balance-a-binary-search-tree](https://leetcode.cn/problems/balance-a-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [balance-a-binary-search-tree](https://leetcode.cn/problems/balance-a-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,null,3,null,4]', '[2,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        def inorder(r):\n",
    "            if r:\n",
    "                inorder(r.left)\n",
    "                stack.append(r)\n",
    "                inorder(r.right)\n",
    "        inorder(root)\n",
    "        n = len(stack)\n",
    "        def buildBST(start, end):\n",
    "            if start > end:\n",
    "                return None\n",
    "            temp = (end - start) // 2 + start\n",
    "            root = stack[temp]\n",
    "            root.left = buildBST(start, temp - 1)\n",
    "            root.right = buildBST(temp + 1, end)\n",
    "            return root\n",
    "        return buildBST(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        result = []\n",
    "        self.midOrder(root, result)\n",
    "        return self.getBalanceTree(result)\n",
    "    \n",
    "    def midOrder(self, root, result):\n",
    "        if root == None:\n",
    "            return\n",
    "        self.midOrder(root.left, result)\n",
    "        result.append(root.val)\n",
    "        self.midOrder(root.right, result)\n",
    "        \n",
    "    def getBalanceTree(self, mylist):\n",
    "        if len(mylist) == 0:\n",
    "            return None\n",
    "        index = len(mylist) // 2\n",
    "        root = TreeNode(mylist[index])\n",
    "        root.left = self.getBalanceTree(mylist[:index])\n",
    "        root.right = self.getBalanceTree(mylist[index+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inOrder(node):\n",
    "            if node.left:\n",
    "                inOrder(node.left)\n",
    "                node.left = None\n",
    "            nodes.append(node)\n",
    "            if node.right:\n",
    "                inOrder(node.right)\n",
    "                node.right = None\n",
    "\n",
    "        def balanceTree(left, right):\n",
    "            mid = (left + right) // 2\n",
    "            pivot = nodes[mid]\n",
    "            if left < mid:\n",
    "                pivot.left = balanceTree(left, mid - 1)\n",
    "            if right > mid:\n",
    "                pivot.right = balanceTree(mid + 1, right)\n",
    "            return pivot\n",
    "        \n",
    "        nodes = []\n",
    "        inOrder(root)\n",
    "        return balanceTree(0, len(nodes) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def getInorder(o):\n",
    "            if o.left:\n",
    "                getInorder(o.left)\n",
    "            inorderSeq.append(o)\n",
    "            if o.right:\n",
    "                getInorder(o.right)\n",
    "        \n",
    "        def build(l, r):\n",
    "            mid = (l + r) // 2\n",
    "            o = inorderSeq[mid]\n",
    "            o.left =  build(l, mid - 1) if l <= mid - 1 else None\n",
    "            o.right = build(mid + 1, r) if mid + 1 <= r else None\n",
    "            return o\n",
    "\n",
    "        inorderSeq = list()\n",
    "        getInorder(root)\n",
    "        return build(0, len(inorderSeq) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        \"\"\" binary search tree my solution\n",
    "        is_balanced(optional): 如果 已经balanced 直接return root\n",
    "        traverse： \n",
    "        \"\"\"\n",
    "        unknown = None\n",
    "        def is_balanced(root):\n",
    "            if not root:\n",
    "                return True, 0\n",
    "            left_balanced, left_height = is_balanced(root.left)\n",
    "            if not left_balanced:\n",
    "                return False, unknown\n",
    "            right_balanced, right_height = is_balanced(root.right)\n",
    "            if not right_balanced:\n",
    "                return False, unknown\n",
    "            return abs(left_height - right_height) <= 1, max(left_height, right_height) + 1\n",
    "        if is_balanced(root)[0]:\n",
    "            return root\n",
    "        sorted_nodes = []\n",
    "        def inorder_traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder_traverse(root.left)\n",
    "            sorted_nodes.append(root)\n",
    "            inorder_traverse(root.right)\n",
    "        inorder_traverse(root)\n",
    "        n = len(sorted_nodes)\n",
    "        def build_balanced_bst(start, end):\n",
    "            if start > end:\n",
    "                return\n",
    "            mid = (start + end) // 2\n",
    "            root = sorted_nodes[mid]\n",
    "            root.left = build_balanced_bst(start, mid - 1)\n",
    "            root.right = build_balanced_bst(mid + 1, end)\n",
    "            return root\n",
    "        return build_balanced_bst(0, n - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        #def is_balanced(root):\n",
    "        #    ...\n",
    "        sorted_nodes = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            traverse(root.left)\n",
    "            sorted_nodes.append(root)\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        n = len(sorted_nodes)\n",
    "        def build_balanced_bst(start, end):\n",
    "            if start > end:\n",
    "                return\n",
    "            mid = (start + end) // 2\n",
    "            root = sorted_nodes[mid]\n",
    "            root.left = build_balanced_bst(start, mid - 1)\n",
    "            root.right = build_balanced_bst(mid + 1, end)\n",
    "            return root\n",
    "        return build_balanced_bst(0, n - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        \"\"\" binary search tree my solution\n",
    "        is_balanced(optional): 如果 已经balanced 直接return root。 同 110. Balanced Binary Tree \n",
    "        inorder_traverse: 中序遍历BST，得到有序的数列\n",
    "        build_balanced_bst：然后用有序数列创建平衡bst：同108. Convert Sorted Array to Binary Search Tree\n",
    "        \"\"\"\n",
    "        unknown = None\n",
    "        def is_balanced(root):\n",
    "            if not root:\n",
    "                return True, 0\n",
    "            left_balanced, left_height = is_balanced(root.left)\n",
    "            if not left_balanced:\n",
    "                return False, unknown\n",
    "            right_balanced, right_height = is_balanced(root.right)\n",
    "            if not right_balanced:\n",
    "                return False, unknown\n",
    "            return abs(left_height - right_height) <= 1, max(left_height, right_height) + 1\n",
    "        if is_balanced(root)[0]:\n",
    "            return root\n",
    "        sorted_nodes = []\n",
    "        def inorder_traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder_traverse(root.left)\n",
    "            sorted_nodes.append(root)\n",
    "            inorder_traverse(root.right)\n",
    "        inorder_traverse(root)\n",
    "        n = len(sorted_nodes)\n",
    "        def build_balanced_bst(start, end):\n",
    "            if start > end:\n",
    "                return\n",
    "            mid = (start + end) // 2\n",
    "            root = sorted_nodes[mid]\n",
    "            root.left = build_balanced_bst(start, mid - 1)\n",
    "            root.right = build_balanced_bst(mid + 1, end)\n",
    "            return root\n",
    "        return build_balanced_bst(0, n - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.balanceBST(root.left)\n",
    "        root.right = self.balanceBST(root.right)\n",
    "        balanceFactor = self.get_height(root.left) - self.get_height(root.right)\n",
    "        if balanceFactor > 1:\n",
    "            lbalance = self.get_height(root.left.left) - self.get_height(root.left.right)\n",
    "            if lbalance < 0:\n",
    "                root.left = self.left_rotate(root.left)\n",
    "            root = self.right_rotate(root)\n",
    "            return self.balanceBST(root)\n",
    "        elif balanceFactor < -1:\n",
    "            rbalance = self.get_height(root.right.left) - self.get_height(root.right.right)\n",
    "            if rbalance > 0:\n",
    "                root.right = self.right_rotate(root.right)\n",
    "            root = self.left_rotate(root)\n",
    "            return self.balanceBST(root)\n",
    "\n",
    "        return root\n",
    "\n",
    "    def get_height(self, node:TreeNode) -> int:\n",
    "        if not node:\n",
    "            return 0\n",
    "        return max(self.get_height(node.left), self.get_height(node.right)) + 1\n",
    "\n",
    "    def left_rotate(self, node:TreeNode):\n",
    "        if not node or (not node.right):\n",
    "            return node\n",
    "        right = node.right\n",
    "        rightleft = node.right.left\n",
    "        node.right = rightleft\n",
    "        right.left = node\n",
    "        return right\n",
    "\n",
    "    def right_rotate(self, node:TreeNode):\n",
    "        if not node or (not node.left):\n",
    "            return node\n",
    "        left = node.left\n",
    "        leftright = node.left.right\n",
    "        node.left = leftright\n",
    "        left.right = node\n",
    "        return left\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def trav(curr):\n",
    "            if curr.left != None:\n",
    "                left = trav(curr.left)\n",
    "            else:\n",
    "                left = []\n",
    "            if curr.right != None:\n",
    "                right = trav(curr.right)\n",
    "            else:\n",
    "                right = []\n",
    "            return left + [curr] + right\n",
    "        trav_list = trav(root)\n",
    "        def build_tree(trav_list):\n",
    "            middle = trav_list[len(trav_list) // 2]\n",
    "            left = trav_list[: len(trav_list) // 2]\n",
    "            right = trav_list[len(trav_list) // 2 + 1:]\n",
    "            if left == []:\n",
    "                middle.left = None\n",
    "            else:\n",
    "                middle.left = left[len(left) // 2]\n",
    "                build_tree(left)\n",
    "            if right == []:\n",
    "                middle.right = None\n",
    "            else:\n",
    "                middle.right = right[len(right) // 2]\n",
    "                build_tree(right)\n",
    "        build_tree(trav_list)\n",
    "        return trav_list[len(trav_list) // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # inorder to get all the nums\n",
    "        self.nodes = []\n",
    "        self.inOrder(root)\n",
    "        # build\n",
    "        bRoot = self.buildBalanceBST(0, len(self.nodes) - 1)\n",
    "\n",
    "        return bRoot\n",
    "    \n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        self.nodes.append(root)\n",
    "        self.inOrder(root.right)\n",
    "    \n",
    "    def buildBalanceBST(self, start, end):\n",
    "        if start > end:\n",
    "            return None\n",
    "        mid = start + (end - start) // 2\n",
    "        root = self.nodes[mid]\n",
    "        root.left = self.buildBalanceBST(start, mid - 1)\n",
    "        root.right = self.buildBalanceBST(mid + 1, end)\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 左旋, 你的左手臂放下来，你的左孩子成为你的新左孩子的右孩子\n",
    "    def leftRotate(self, root) -> TreeNode:\n",
    "        # TODO 注意啊现在输入的是根节点，也就是说不是中间那个, 所以必须有右孩子！不然肯定不旋!\n",
    "        if root is None or root.right is None: return root \n",
    "        \n",
    "        RIGHT = root.right # 事后的根节点\n",
    "        \n",
    "        # root要成为RIGHT的左孩子\n",
    "        RIGHT_LEFT = RIGHT.left # 保留原来的左孩子\n",
    "        RIGHT.left = root # root成为RIGHT的左孩子\n",
    "        root.right = RIGHT_LEFT # RIGHT的原左孩子成为root的右孩子\n",
    "\n",
    "        return RIGHT\n",
    "\n",
    "\n",
    "    # 右旋，你的右手臂放下来，你的右孩子成为你的新右孩子的左孩子\n",
    "    def rightRotate(self, root) -> TreeNode:\n",
    "        # 现在输入的是根节点，也就是/ 右上角那个。\n",
    "        if root is None or root.left is None: return root\n",
    "\n",
    "        LEFT = root.left # 事后的根节点\n",
    "\n",
    "        # root要成为LEFT的右孩子\n",
    "        LEFT_RIGHT = LEFT.right # 保存原右孩子\n",
    "        LEFT.right = root # root 成为 LEFT右孩子\n",
    "        root.left = LEFT_RIGHT # LEFT的原右孩子成为root的左孩子\n",
    "\n",
    "        return LEFT\n",
    "\n",
    "    # 获取树的高度(好简洁。。)\n",
    "    def getHeight(self, root) -> int:\n",
    "        if root is None: return 0\n",
    "        return max(self.getHeight(root.left), self.getHeight(root.right)) + 1\n",
    "\n",
    "    # 使得二叉搜索树变成平衡二叉搜索树(后序遍历，因为要从最下层往上看)\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 递归出口\n",
    "        if root is None: return root\n",
    "\n",
    "        # 左右\n",
    "        root.left = self.balanceBST(root.left)\n",
    "        root.right = self.balanceBST(root.right)\n",
    "\n",
    "        # 中\n",
    "        balanceFactor = self.getHeight(root.left) - self.getHeight(root.right) # 求左右子树高度差\n",
    "        if balanceFactor > 1:\n",
    "            # 左子树太高\n",
    "            leftBalanceFactor = self.getHeight(root.left.left) - self.getHeight(root.left.right)\n",
    "            if leftBalanceFactor < 0:\n",
    "                # root左子树高, root.left右子树高，说明出现了折线，root.left需要下沉\n",
    "                # (记住其实不论是左旋还是右旋只针对两个就值好了，其他的不用管，自然协调)\n",
    "                root.left = self.leftRotate(root.left) # \n",
    "            # 现在就是规范的/了\n",
    "            root = self.rightRotate(root)\n",
    "            return self.balanceBST(root) # TODO 为什么要再来一次？？？ 因为可能整棵树严重不平衡。。\n",
    "        elif balanceFactor < -1: \n",
    "            # 右子树太高， 最舒服的情况是\\\n",
    "            \n",
    "            # 看看有没有出现折线\n",
    "            rightBalanceFactor = self.getHeight(root.right.left) - self.getHeight(root.right.right)\n",
    "            if rightBalanceFactor > 0:\n",
    "                # 出现了折线\n",
    "                root.right = self.rightRotate(root.right)\n",
    "            # 已经是最舒服的情况\\了\n",
    "            root = self.leftRotate(root)\n",
    "            return self.balanceBST(root) # TODO 为什么要再来一次？？？因为可能整棵树严重不平衡。。 \n",
    "             \n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.res = []\n",
    "        self.inOrder(root)\n",
    "        return self.listtoBST(self.res)\n",
    "\n",
    "    def listtoBST(self, list):\n",
    "        if not list:\n",
    "            return\n",
    "        self.len = len(list)\n",
    "        mid = self.len // 2\n",
    "        root = TreeNode(list[mid])\n",
    "        root.left = self.listtoBST(list[:mid])\n",
    "        root.right = self.listtoBST(list[mid+1:])\n",
    "        return root\n",
    "\n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        self.res.append(root.val)\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def build(self, array):\n",
    "        if not array:\n",
    "            return None\n",
    "        n = len(array)\n",
    "        if n == 1:\n",
    "            root = TreeNode(array[0])\n",
    "            return root\n",
    "        mid = n // 2\n",
    "        root = TreeNode(array[mid])\n",
    "        left = self.build(array[:mid])\n",
    "        right = self.build(array[mid+1:])\n",
    "        root.left = left\n",
    "        root.right = right\n",
    "        return root\n",
    "        \n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        array = []\n",
    "        stack = []\n",
    "        while stack or root:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                array.append(node.val)\n",
    "                root = node.right\n",
    "        \n",
    "        return self.build(array)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.nodes = []\n",
    "        self.inOrder(root)\n",
    "        bRoot = self.buildBalanceBST(0, len(self.nodes) - 1)\n",
    "        return bRoot\n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        self.nodes.append(root)\n",
    "        self.inOrder(root.right)\n",
    "    def buildBalanceBST(self, start, end):\n",
    "        if start > end:\n",
    "            return None\n",
    "        mid = start + (end - start) // 2\n",
    "        root = self.nodes[mid]\n",
    "        root.left = self.buildBalanceBST(start, mid - 1)\n",
    "        root.right = self.buildBalanceBST(mid + 1, end)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # \n",
    "        unknown = None\n",
    "        def is_balanced(root):\n",
    "            if not root:\n",
    "                return True, 0\n",
    "            left_balanced, left_height = is_balanced(root.left)\n",
    "            if not left_balanced:\n",
    "                return False, unknown\n",
    "            right_balanced, right_height = is_balanced(root.right)\n",
    "            if not right_balanced:\n",
    "                return False, unknown\n",
    "            return abs(left_height - right_height) <= 1, max(left_height, right_height) + 1\n",
    "        if is_balanced(root)[0]:\n",
    "            return root\n",
    "        sorted_nodes = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            traverse(root.left)\n",
    "            sorted_nodes.append(root)\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        n = len(sorted_nodes)\n",
    "        def build_balanced_bst(start, end):\n",
    "            if start > end:\n",
    "                return\n",
    "            mid = (start + end) // 2\n",
    "            root = sorted_nodes[mid]\n",
    "            root.left = build_balanced_bst(start, mid - 1)\n",
    "            root.right = build_balanced_bst(mid + 1, end)\n",
    "            return root\n",
    "        return build_balanced_bst(0, n - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def helper(self, current: TreeNode):\n",
    "        if current == None:\n",
    "            pass\n",
    "        elif current.left == None and current.right == None:\n",
    "            self.all_nodes.append(current)\n",
    "        else:\n",
    "            self.helper(current.left)\n",
    "            self.all_nodes.append(current)\n",
    "            self.helper(current.right)\n",
    "    def sorting(self, nodes: List):\n",
    "        if nodes == None or len(nodes) == 0:\n",
    "            return None\n",
    "        mid = int(len(nodes) / 2)\n",
    "        print(mid, len(nodes))\n",
    "        root = nodes[mid]\n",
    "        root.left = self.sorting(nodes[0:mid])\n",
    "        root.right = self.sorting(nodes[mid+1:])\n",
    "        return root\n",
    "    # def sorting(self, nums: List):\n",
    "    #     if not nums: \n",
    "    #         return None\n",
    "        # mid = (len(nums) - 1) // 2\n",
    "    #     root = nums[mid]\n",
    "    #     root.left = self.sorting(nums[:mid])\n",
    "    #     root.right = self.sorting(nums[mid + 1:])\n",
    "    #     return root\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.all_nodes = []\n",
    "        self.helper(root)\n",
    "        print([node.val for node in self.all_nodes])\n",
    "        for node in self.all_nodes:\n",
    "            node.left = None\n",
    "            node.right = None\n",
    "        mid = int(len(self.all_nodes) / 2 - 0.5)\n",
    "        root = self.sorting(self.all_nodes)\n",
    "        return root\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            ans.append(root)\n",
    "            dfs(root.right)\n",
    "            root.left = None\n",
    "            root.right = None\n",
    "        dfs(root)\n",
    "\n",
    "        def bulid(nums):\n",
    "            if not nums:\n",
    "                return None\n",
    "            n = len(nums)\n",
    "            root = nums[n // 2]\n",
    "            root.left = bulid(nums[:n // 2])\n",
    "            root.right = bulid(nums[n // 2 + 1:])\n",
    "            return root\n",
    "\n",
    "        return bulid(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inOrder(node):\n",
    "            if not node:\n",
    "                return\n",
    "            inOrder(node.left)\n",
    "            nodeList.append(node)\n",
    "            inOrder(node.right)\n",
    "\n",
    "        def list2Tree(lst):\n",
    "            if not lst:\n",
    "                return None\n",
    "            n = len(lst)\n",
    "            root = lst[n//2]\n",
    "            root.left = list2Tree(lst[:n//2])\n",
    "            root.right = list2Tree(lst[n//2+1:])\n",
    "            return root\n",
    "\n",
    "        nodeList = []\n",
    "        inOrder(root)\n",
    "        return list2Tree(nodeList)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inOrder(self, root, res):\n",
    "        if root == None:\n",
    "            return \n",
    "\n",
    "        self.inOrder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.inOrder(root.right, res)\n",
    "\n",
    "    def process(self, res, left, right):\n",
    "        if left > right:\n",
    "            return None\n",
    "        mid = (left + right) // 2\n",
    "        midNode = TreeNode(res[mid])\n",
    "        midNode.left = self.process(res, left, mid - 1)\n",
    "        midNode.right = self.process(res, mid + 1, right)\n",
    "        return midNode\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        self.inOrder(root,res)\n",
    "        return self.process(res, 0, len(res) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traverse(root.left)\n",
    "        self.vec.append(root.val)\n",
    "        self.traverse(root.right)\n",
    "\n",
    "    def getTree(self, left, right):\n",
    "        if left > right:\n",
    "            return None\n",
    "        mid = (left + right) // 2\n",
    "        root = TreeNode(self.vec[mid])\n",
    "        root.left = self.getTree(left, mid - 1)\n",
    "        root.right = self.getTree(mid + 1, right)\n",
    "        return root\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.vec = []\n",
    "        self.traverse(root)\n",
    "        return self.getTree(0, len(self.vec) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getSortedList(self, root, result):\n",
    "        if not root:\n",
    "            return\n",
    "        self.getSortedList(root.left, result)\n",
    "        result.append(root.val)\n",
    "        self.getSortedList(root.right, result)\n",
    "\n",
    "    def buildTree(self, arr, left, right):\n",
    "        if left > right:\n",
    "            return\n",
    "\n",
    "        mid = (left+right) // 2\n",
    "        root = TreeNode(arr[mid])\n",
    "        root.left = self.buildTree(arr, left, mid-1)\n",
    "        root.right = self.buildTree(arr, mid+1, right)\n",
    "\n",
    "        return root\n",
    "    \n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        values = []\n",
    "        self.getSortedList(root, values)\n",
    "        return self.buildTree(values, 0, len(values)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inOrder(self, root, nums):\n",
    "        if root == None:\n",
    "            return None\n",
    "        self.inOrder(root.left, nums)\n",
    "        nums.append(root.val)\n",
    "        self.inOrder(root.right, nums)\n",
    "\n",
    "    def process(self, nums, left, right):\n",
    "        if left > right:\n",
    "            return None\n",
    "        mid = (left+right)//2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.process(nums, left, mid-1)\n",
    "        root.right = self.process(nums, mid+1, right)\n",
    "        return root\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        self.inOrder(root, nums)\n",
    "        return self.process(nums, 0, len(nums) -1)\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 先将二叉树变成有序数组\n",
    "        # 然后根据有序数组构建平衡二叉搜索树\n",
    "\n",
    "        res = []\n",
    "        def traversal(node):\n",
    "            if not node:\n",
    "                return\n",
    "            traversal(node.left)\n",
    "            res.append(node.val)\n",
    "            traversal(node.right)\n",
    "    \n",
    "        def getTree(nums, left, right):\n",
    "            if left>right:\n",
    "                return\n",
    "            \n",
    "            mid = (right-left)//2+left\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = getTree(nums, left, mid-1)\n",
    "            root.right = getTree(nums, mid+1, right)\n",
    "            return root\n",
    "    \n",
    "        traversal(root)\n",
    "        return getTree(res, 0, len(res)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        lis = self.inorder(root)\n",
    "        head = self.crearAvlTree(lis,0,len(lis)-1)\n",
    "        return head\n",
    "    def crearAvlTree(self,lis,left,right):\n",
    "        if left > right:\n",
    "            return \n",
    "        mid = left + (right-left)//2\n",
    "        head = TreeNode(lis[mid])\n",
    "        head.left = self.crearAvlTree(lis,left,mid-1)\n",
    "        head.right = self.crearAvlTree(lis,mid+1,right)\n",
    "        return head\n",
    "    def inorder(self,root):\n",
    "        ans = []\n",
    "        tmp = []\n",
    "        cur = root\n",
    "        while tmp or cur:\n",
    "            if cur:\n",
    "                tmp.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = tmp.pop()\n",
    "                ans.append(cur.val)\n",
    "                cur = cur.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def to_order(self, root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return self.to_order(root.left) + [root.val] + self.to_order(root.right)\n",
    "\n",
    "    def arr_to_balance(self, arr, left, right):\n",
    "        if left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            node = TreeNode(val = arr[mid])\n",
    "            node.left = self.arr_to_balance(arr, left, mid - 1)\n",
    "            node.right = self.arr_to_balance(arr, mid + 1, right)\n",
    "            return node\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return \n",
    "        order_list = self.to_order(root)\n",
    "        print(order_list)\n",
    "        return self.arr_to_balance(order_list, 0, len(order_list) - 1)\n",
    "        \n",
    "    # zjj\n",
    "    # 先转有序数组，在二分平衡之"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            node_list.append(root.val)\n",
    "            inorder(root.right)\n",
    "\n",
    "        def create_tree(node_list, left, right):\n",
    "            if left>right:\n",
    "                return None\n",
    "            mid = left+(right-left)//2\n",
    "            node = TreeNode(node_list[mid])\n",
    "            node.left = create_tree(node_list, left, mid-1)\n",
    "            node.right = create_tree(node_list, mid+1, right)\n",
    "            return node\n",
    "\n",
    "        node_list = []\n",
    "        inorder(root)\n",
    "        print(len(node_list))\n",
    "        return create_tree(node_list, 0, len(node_list)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        sortedList = []\n",
    "        def inorder(node):\n",
    "\n",
    "            if not node:\n",
    "                return \n",
    "            \n",
    "            inorder(node.left)\n",
    "            sortedList.append(node.val)\n",
    "            inorder(node.right)\n",
    "        \n",
    "        inorder(root)\n",
    "\n",
    "        #print(sortedList)\n",
    "\n",
    "        def buildTree(l, r):\n",
    "\n",
    "            if l > r:\n",
    "                return None\n",
    "\n",
    "            mid = (l+r)>>1\n",
    "\n",
    "            root = TreeNode(sortedList[mid])\n",
    "            root.left = buildTree(l, mid - 1)\n",
    "            root.right = buildTree(mid + 1, r)\n",
    "\n",
    "            return root\n",
    "        return buildTree(0, len(sortedList)-1)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            left, right = inorder(node.left), inorder(node.right)\n",
    "            return left + [node.val] + right \n",
    "        \n",
    "        def build(l, r):\n",
    "            if l > r:\n",
    "                return None \n",
    "            mid = l + ((r - l) >> 1)\n",
    "            root = TreeNode(lst[mid])\n",
    "            root.left = build(l, mid - 1)\n",
    "            root.right = build(mid + 1, r)\n",
    "            return root \n",
    "\n",
    "        lst = inorder(root)\n",
    "        n = len(lst)\n",
    "        return build(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        # 有序树转成有序数组\n",
    "        def traversal(cur: TreeNode):\n",
    "            if not cur: return\n",
    "            traversal(cur.left)\n",
    "            res.append(cur.val)\n",
    "            traversal(cur.right)\n",
    "        # 有序数组转成平衡二叉树\n",
    "        def getTree(nums: List, left, right):\n",
    "            if left > right: return \n",
    "            mid = left + (right -left) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = getTree(nums, left, mid - 1)\n",
    "            root.right = getTree(nums, mid + 1, right)\n",
    "            return root\n",
    "        traversal(root)\n",
    "        return getTree(res, 0, len(res) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.record = []\n",
    "    def traversal(self, span: list):\n",
    "        if not span:\n",
    "            return None\n",
    "        index = len(span) // 2\n",
    "        node = TreeNode(val=span[index])\n",
    "        node.left = self.traversal(span[:index])\n",
    "        node.right = self.traversal(span[index + 1:])\n",
    "        return node\n",
    "    def ergodic(self, root: TreeNode):\n",
    "        if not root:\n",
    "            return \n",
    "        self.ergodic(root.left)\n",
    "        self.record.append(root.val)\n",
    "        self.ergodic(root.right)\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.ergodic(root)\n",
    "        node = self.traversal(self.record[:])\n",
    "        return node\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def traversal(cur):\n",
    "            if not cur:    return\n",
    "            traversal(cur.left)\n",
    "            nums.append(cur.val)\n",
    "            traversal(cur.right)\n",
    "\n",
    "        def creadBST(nums, l, r):\n",
    "            if l > r:   return\n",
    "            mid = (l+r) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = creadBST(nums, l, mid-1)\n",
    "            root.right = creadBST(nums, mid+1, r)\n",
    "            return root\n",
    "        \n",
    "        traversal(root)\n",
    "        return creadBST(nums, 0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "\n",
    "        def traversal(root):\n",
    "            if root.left:\n",
    "                traversal(root.left)\n",
    "            nums.append(root.val)\n",
    "            if root.right:\n",
    "                traversal(root.right)\n",
    "        traversal(root)\n",
    "        print(nums)\n",
    "        def find(nums):\n",
    "            if len(nums) == 0: return None\n",
    "            idx = len(nums) // 2\n",
    "            root = TreeNode(nums[idx])\n",
    "            root.left = find(nums[:idx])\n",
    "            root.right = find(nums[idx+1:])\n",
    "            return root\n",
    "\n",
    "        return find(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        sorted_tree = []\n",
    "        def inorder_travel(root):\n",
    "            if not root:\n",
    "                return \n",
    "            # 中序遍历\n",
    "            inorder_travel(root.left)\n",
    "            sorted_tree.append(root.val)\n",
    "            inorder_travel(root.right)\n",
    "        inorder_travel(root)\n",
    "        print(sorted_tree)\n",
    "        def list2tree(sorted_tree):\n",
    "            if len(sorted_tree) == 0:\n",
    "                return None\n",
    "            mid = len(sorted_tree)//2\n",
    "            root = TreeNode()\n",
    "            root.val = sorted_tree[mid]\n",
    "            root.left = list2tree(sorted_tree[:mid])\n",
    "            root.right = list2tree(sorted_tree[mid+1:])\n",
    "            return root\n",
    "        new_root = list2tree(sorted_tree)\n",
    "        return new_root\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def to_nums(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left:\n",
    "                to_nums(root.left)\n",
    "            res.append(root.val)\n",
    "            if root.right:\n",
    "                to_nums(root.right)\n",
    "        def to_tree(nums):\n",
    "            if not len(nums):\n",
    "                return None\n",
    "            index = len(nums) // 2\n",
    "            root = TreeNode(nums[index])\n",
    "            root.left = to_tree(nums[:index])\n",
    "            root.right = to_tree(nums[index+1:])\n",
    "            return root\n",
    "        res = []\n",
    "        to_nums(root)\n",
    "        return to_tree(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        def backtracking(root):\n",
    "            if not root: return None\n",
    "            left = backtracking(root.left)\n",
    "            res.append(root.val)\n",
    "            right = backtracking(root.right)\n",
    "        backtracking(root)\n",
    "        # print(res)\n",
    "        def construct(res):\n",
    "            if not res:return None\n",
    "            n = len(res)\n",
    "            index = int(n / 2)\n",
    "            root1 = TreeNode()\n",
    "            root1.val = res[index]\n",
    "            root1.left = construct(res[:index])\n",
    "            root1.right = construct(res[index + 1:])\n",
    "            return root1\n",
    "        return construct(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        temp = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur:\n",
    "                if cur.right:\n",
    "                    stack.append(cur.right)\n",
    "                stack.append(cur)\n",
    "                stack.append(None)\n",
    "                if cur.left:\n",
    "                    stack.append(cur.left)\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                temp.append(cur.val)\n",
    "        # print(temp)\n",
    "        return self.gettree(temp, 0, len(temp)-1)\n",
    "    def gettree(self, nums, left, right):\n",
    "        if left > right:\n",
    "            return None\n",
    "        mid = left + (right - left) // 2\n",
    "        mid_root = TreeNode(nums[mid])\n",
    "        mid_root.left = self.gettree(nums, left, mid-1)\n",
    "        mid_root.right = self.gettree(nums, mid+1, right)\n",
    "        return mid_root\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def infind(node):\n",
    "            ret = []\n",
    "            if node.left:\n",
    "                ret += infind(node.left)\n",
    "            ret.append(node.val)\n",
    "            if node.right:\n",
    "                ret += infind(node.right)\n",
    "            return ret\n",
    "        def fuc(l, r):\n",
    "            if l > r:\n",
    "                return None\n",
    "            mid = l + (r - l) // 2\n",
    "            node = TreeNode(nums[mid])\n",
    "            node.left = fuc(l, mid - 1)\n",
    "            node.right = fuc(mid + 1, r)\n",
    "            return node       \n",
    "        nums = infind(root)\n",
    "        print(nums)\n",
    "        return fuc(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def infind(node):\n",
    "            ret = []\n",
    "            if node.left:\n",
    "                ret += infind(node.left)\n",
    "            ret.append(node.val)\n",
    "            if node.right:\n",
    "                ret += infind(node.right)\n",
    "            return ret\n",
    "        def fuc(l, r):\n",
    "            if l > r:\n",
    "                return None\n",
    "            mid = l + (r - l) // 2\n",
    "            node = TreeNode(nums[mid])\n",
    "            node.left = fuc(l, mid - 1)\n",
    "            node.right = fuc(mid + 1, r)\n",
    "            return node       \n",
    "        nums = infind(root)\n",
    "        print(nums)\n",
    "        return fuc(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums=[]\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            node=stack.pop()\n",
    "            if node:\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)    \n",
    "            else:\n",
    "                cur=stack.pop()\n",
    "                nums.append(cur.val)\n",
    "        lt,rt=0,len(nums)\n",
    "        def fun(lt,rt):\n",
    "            if lt>=rt:\n",
    "                return None\n",
    "            mid=lt+(rt-lt)//2\n",
    "            cur= TreeNode(val=nums[mid])    \n",
    "            cur.left=fun(lt,mid)   \n",
    "            cur.right=fun(mid+1,rt)    \n",
    "            return cur\n",
    "        return fun(lt,rt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.nums = []\n",
    "        self.traversal(root)\n",
    "        return self.build(self.nums)\n",
    "    def traversal(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traversal(root.left)\n",
    "        self.nums.append(root.val)\n",
    "        self.traversal(root.right)\n",
    "        return\n",
    "    def build(self,nums):\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        idx = len(nums) // 2\n",
    "        val = nums[idx]\n",
    "        node = TreeNode(val)\n",
    "        if len(nums) == 1:\n",
    "            return node\n",
    "        node.left = self.build(nums[:idx])\n",
    "        node.right = self.build(nums[idx+1:])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def height(self,root:TreeNode):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return max(self.height(root.left),self.height(root.right))+1\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        list=[]\n",
    "        def travel(root:TreeNode):\n",
    "            if root is None:\n",
    "                return\n",
    "            travel(root.left)\n",
    "            list.append(root.val)\n",
    "            travel(root.right)\n",
    "        def build(low:int,high:int)->TreeNode:\n",
    "            if low>high:\n",
    "                return None\n",
    "            temp_val=int((low+high)/2)\n",
    "            root=TreeNode(list[temp_val])\n",
    "            root.left=build(low,temp_val-1)\n",
    "            root.right=build(temp_val+1,high)\n",
    "            return root\n",
    "        travel(root)\n",
    "        print(list)\n",
    "        return  build(0,len(list)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def infind(node):\n",
    "            ret = []\n",
    "            if node.left:\n",
    "                ret += infind(node.left)\n",
    "            ret.append(node.val)\n",
    "            if node.right:\n",
    "                ret += infind(node.right)\n",
    "            return ret\n",
    "        def fuc(l, r):\n",
    "            if l > r:\n",
    "                return None\n",
    "            mid = l + (r - l) // 2\n",
    "            node = TreeNode(nums[mid])\n",
    "            node.left = fuc(l, mid - 1)\n",
    "            node.right = fuc(mid + 1, r)\n",
    "            return node       \n",
    "        nums = infind(root)\n",
    "        print(nums)\n",
    "        return fuc(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 思路：先将二叉搜索树转为中序遍历序列，再根据中序遍历序列转化为平衡二叉搜索树\n",
    "\n",
    "        def turn_series(root):\n",
    "            # 将二叉搜索树转化为中序遍历序列\n",
    "            res = []\n",
    "            if root == None: return res\n",
    "            stack = []\n",
    "            cur = root\n",
    "            \n",
    "            while cur or stack:\n",
    "                if cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur = stack.pop()\n",
    "                    res.append(cur.val)\n",
    "                    cur = cur.right\n",
    "            return res\n",
    "\n",
    "        def construct_tree(i, j):\n",
    "            # 将序列的i到j部分转化为平衡二叉搜索树\n",
    "            if i > j: return None\n",
    "            m = (i + j) // 2\n",
    "            root = TreeNode(series[m])  # 序列中间值元素构建根节点\n",
    "            root.left = construct_tree(i, m-1)\n",
    "            root.right = construct_tree(m+1, j)\n",
    "            return root\n",
    "\n",
    "\n",
    "        series = turn_series(root)  # 将原树转化为序列\n",
    "        print(series)\n",
    "        new_tree = construct_tree(0, len(series)-1)  # 将序列构建为平衡二叉搜索树\n",
    "        return new_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # def InorderTravesal(root):\n",
    "        #     if not root:\n",
    "        #         return \n",
    "        #     InorderTravesal(root.left)\n",
    "        #     inorder.append(root.val)\n",
    "        #     InorderTravesal(root.right)\n",
    "\n",
    "        # def buildTree(l, r):\n",
    "        #     if l > r:\n",
    "        #         return\n",
    "        #     mid = (l+r) // 2\n",
    "        #     node = TreeNode(inorder[mid])\n",
    "        #     node.left = buildTree(l, mid-1)\n",
    "        #     node.right = buildTree(mid+1, r)\n",
    "        #     return node\n",
    "            \n",
    "        # inorder = []\n",
    "        # InorderTravesal(root)\n",
    "        # return buildTree(0, len(inorder)-1)\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return\n",
    "            helper(root.left)\n",
    "            inorder.append(root.val)\n",
    "            helper(root.right)\n",
    "        def getlen(n):\n",
    "            tmp = n + 1\n",
    "            h = 0\n",
    "            while tmp != 1:\n",
    "                tmp //= 2\n",
    "                h += 1\n",
    "            x = n - 2**h + 1\n",
    "            x = x if x < 2**(h-1) else 2**(h-1)\n",
    "            return 2**(h-1)-1+x\n",
    "        def solve(l, r, idx):\n",
    "            n = r - l + 1\n",
    "            if n == 0:\n",
    "                return\n",
    "            L = getlen(n)\n",
    "            t[idx] = inorder[L+l]\n",
    "            lidx = idx*2 + 1\n",
    "            solve(l, l+L-1, lidx)\n",
    "            solve(l+L+1, r, lidx+1)\n",
    "        inorder = []\n",
    "        helper(root)\n",
    "\n",
    "        t = [0]*len(inorder)\n",
    "        solve(0, len(inorder)-1, 0)\n",
    "        def createTree(i):\n",
    "            if i > len(t) - 1:\n",
    "                return None\n",
    "            node = TreeNode(t[i])\n",
    "            if i*2+1 <= len(t) - 1:\n",
    "                node.left = createTree(i*2+1)\n",
    "            if i * 2 + 2 <= len(t) - 1:\n",
    "                node.right = createTree(i*2+2)\n",
    "            return node\n",
    "        return createTree(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        # if not root:\n",
    "        #     return root\n",
    "        \n",
    "        # all_node = [root]\n",
    "        # result = []\n",
    "        # # 首先获取root的遍历\n",
    "        # while all_node:\n",
    "        #     node = all_node.pop()\n",
    "        #     if node:\n",
    "        #         if node.left:\n",
    "        #             all_node.append(node.left)\n",
    "        #         all_node.append(node)\n",
    "        #         all_node.append(None)\n",
    "        #         if node.right:\n",
    "        #             all_node.append(node.right)\n",
    "        #     else:\n",
    "        #         node = all_node.pop()\n",
    "        #         node.left = None\n",
    "        #         node.right = None\n",
    "        #         result.append(node)\n",
    "        # print('result: ', [node.val for node in result])\n",
    "        # # 然后构建平衡树,循环了,还是有点混乱\n",
    "        # # 用暴力法,留着这道题目\n",
    "\n",
    "        # # 利用中序遍历构建树,草稿纸看一下，平衡树要求是二叉树\n",
    "        # def travel(cur):\n",
    "        #     mid = int(len(cur) / 2)\n",
    "        #     left = cur[:mid]\n",
    "        #     right = cur[mid+1:]\n",
    "            \n",
    "        #     left_tree = None\n",
    "        #     right_tree = None\n",
    "        #     if left:\n",
    "        #         left_tree = travel(left)\n",
    "        #     if right:\n",
    "        #         right_tree = travel(right)\n",
    "        #     cur[mid].left = right_tree\n",
    "        #     cur[mid].right = left_tree\n",
    "\n",
    "        #     return cur[mid]\n",
    "\n",
    "        # return travel(result)\n",
    "\n",
    "        if not root:\n",
    "            return root\n",
    "        # print('root: ', root)\n",
    "        res = []\n",
    "        # 用回溯的方式试试\n",
    "        def travel(cur):\n",
    "            if not cur: return \n",
    "            travel(cur.left)\n",
    "            res.append(cur.val)\n",
    "            travel(cur.right)\n",
    "        \n",
    "        # 由中节点构建\n",
    "        def getTree(left, right):\n",
    "            if left > right:\n",
    "                return \n",
    "            mid = int((left+right)/2)\n",
    "            \n",
    "            root = TreeNode(res[mid])\n",
    "            \n",
    "            root.left = getTree(left, mid-1)\n",
    "            root.right = getTree(mid+1, right)\n",
    "\n",
    "            return root\n",
    "        \n",
    "        travel(root)\n",
    "        print(res)\n",
    "        return getTree(0, len(res)-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans=[]\n",
    "        def inOrder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inOrder(root.left)\n",
    "            ans.append(root.val)\n",
    "            inOrder(root.right)\n",
    "   \n",
    "        def createBST(ans,left,right):\n",
    "            if left>right:\n",
    "                return None\n",
    "            mid = (left+right)//2\n",
    "            print(left,right)\n",
    "            print(mid)\n",
    "            temp_root = TreeNode(ans[mid])\n",
    "            temp_root.left = createBST(ans,left,mid-1)\n",
    "            temp_root.right=createBST(ans,mid+1,right)\n",
    "            return temp_root\n",
    "        inOrder(root)\n",
    "        print(ans)\n",
    "        res=createBST(ans,0,len(ans)-1)\n",
    "        print(res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mid_visit_tree(self, root: TreeNode, order_list):\n",
    "        if root.left is not None:\n",
    "            self.mid_visit_tree(root.left, order_list)\n",
    "        if root is not None:\n",
    "            order_list.append(root.val)\n",
    "        else:\n",
    "            return\n",
    "        if root.right is not None:\n",
    "            self.mid_visit_tree(root.right, order_list)\n",
    "\n",
    "    def turn_order_list_to_tree(self, root: TreeNode, order_list):\n",
    "        root.left = TreeNode(None)\n",
    "        root.right = TreeNode(None)\n",
    "        if len(order_list) == 1:\n",
    "            root.val = order_list[0]            \n",
    "            return\n",
    "        else:\n",
    "            root.val = order_list[len(order_list) // 2]        \n",
    "        self.turn_order_list_to_tree(root.left, order_list[0:len(order_list) // 2])\n",
    "        if len(order_list) == 2:\n",
    "            return        \n",
    "        self.turn_order_list_to_tree(root.right, order_list[len(order_list) // 2 + 1: len(order_list)])\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        order_list = []\n",
    "        self.mid_visit_tree(root, order_list)\n",
    "        print(order_list)\n",
    "        new_root = TreeNode(None)\n",
    "        self.turn_order_list_to_tree(new_root, order_list)\n",
    "        print(new_root.val)\n",
    "        print(new_root.left.val)\n",
    "        print(new_root.right.val)\n",
    "        return new_root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        seq = []\n",
    "        def getInorder(root):\n",
    "            if root.left:\n",
    "                getInorder(root.left)\n",
    "            seq.append(root.val)\n",
    "            if root.right:\n",
    "                getInorder(root.right)\n",
    "        getInorder(root)\n",
    "        # for i in range(len(seq)):\n",
    "            # print(i)\n",
    "        def build(left, right):\n",
    "            mid = (left + right)//2\n",
    "            print(mid)\n",
    "            root = TreeNode(seq[mid])\n",
    "            print(root)\n",
    "            if left <= mid -1:\n",
    "                root.left = build(left, mid-1)\n",
    "            if mid + 1 <= right:\n",
    "                root.right = build(mid +1 ,right)\n",
    "            return root\n",
    "            # getInorder(root)\n",
    "        output = build(0, len(seq) - 1)\n",
    "        print(output)\n",
    "        return output\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "#         def getInorder(o):\n",
    "#             if o.left:\n",
    "#                 getInorder(o.left)\n",
    "#             inorderSeq.append(o.val)\n",
    "#             if o.right:\n",
    "#                 getInorder(o.right)\n",
    "        \n",
    "#         def build(l, r):\n",
    "#             mid = (l + r) // 2\n",
    "#             o = TreeNode(inorderSeq[mid])\n",
    "#             if l <= mid - 1:\n",
    "#                 o.left = build(l, mid - 1)\n",
    "#             if mid + 1 <= r:\n",
    "#                 o.right = build(mid + 1, r)\n",
    "#             return o\n",
    "\n",
    "#         inorderSeq = list()\n",
    "#         getInorder(root)\n",
    "#         return build(0, len(inorderSeq) - 1)\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/balance-a-binary-search-tree/solution/jiang-er-cha-sou-suo-shu-bian-ping-heng-by-leetcod/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        stack = []\n",
    "        p = root\n",
    "\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            if stack:\n",
    "                node = stack.pop()\n",
    "                nums.append(node.val)\n",
    "                p = node.right\n",
    "        return self.build_tree(nums)\n",
    "\n",
    "    def build_tree(self, nums):\n",
    "        if not nums:\n",
    "            return TreeNode(None)\n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.build_tree(nums[:mid])\n",
    "        root.right = self.build_tree(nums[mid+1:])\n",
    "       \n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        dic={}\n",
    "        dic=collections.defaultdict(int)\n",
    "        #functions\n",
    "        def getheight(root):\n",
    "            \n",
    "            return max(dic[root.left],dic[root.right])+1\n",
    "        def isavl(root):\n",
    "            return abs(dic[root.left]-dic[root.right])<2\n",
    "        def insert(root,val):\n",
    "            if not root:\n",
    "                #true insert\n",
    "                root=TreeNode(val)\n",
    "                dic[root]=1\n",
    "                #need to update height\n",
    "                #return root\n",
    "            else:\n",
    "                #先insert 完值  然后再判断是否为超过height  这里有个逻辑问题\n",
    "                #对于当前root节点，先查看他是走左边节点还是右边  \n",
    "                #然后要是走左边，判断走左边还是右边 -- LL LR情况 ，如果LR，则给他Insert进去 然后再进行左旋，旋转再右旋：：\n",
    "                #这里使用递归来做 ，问题就出在了这里了。 不管那么多 出来了再检查\n",
    "                if val<root.val:\n",
    "                    root.left=insert(root.left,val)\n",
    "                    if not isavl(root):\n",
    "                        #LR情况    \n",
    "                        if val > root.left.val:\n",
    "                            #leftr first\n",
    "                            root.left=leftr(root.left)\n",
    "                        #LL情况  这里 记住 ，root对应 节点是变的\n",
    "                        root=rightr(root)\n",
    "                elif val >root.val:\n",
    "                    root.right=insert(root.right,val)\n",
    "                    if not isavl(root):\n",
    "                        if val < root.right.val:\n",
    "                            root.right=rightr(root.right)\n",
    "                        root=leftr(root) \n",
    "                else:#same node\n",
    "                    return root\n",
    "            #update height recursively\n",
    "            #在这里更新 需要想的一个问题是 当他们在旋转过程中，切换了root节点的位置时 是否会有冲突 造成影响\n",
    "            dic[root]=getheight(root)\n",
    "            return root\n",
    "\n",
    "                    \n",
    "        #返回的是 旋转后的节点值            \n",
    "        def leftr(root):\n",
    "            right=root.right\n",
    "            root.right=right.left\n",
    "            right.left=root\n",
    "            #update root\n",
    "            #rooth=getheight(root)\n",
    "            dic[root]=getheight(root)\n",
    "            #\n",
    "            dic[right]=getheight(right)\n",
    "            return right\n",
    "        def rightr(root):\n",
    "            left=root.left\n",
    "            root.left=left.right\n",
    "            left.right=root\n",
    "            dic[root]=getheight(root)\n",
    "            dic[left]=getheight(left)\n",
    "            return left\n",
    "        #首先 我们要定义左旋右旋，我差不多也知道\n",
    "        #OK 30分钟 解决手撕AVL的问题好吗 不做完不吃饭\n",
    "        #注意了，首先打好基础： right left | insert |\n",
    "\n",
    "\n",
    "\n",
    "        #################遍历 获取节点\n",
    "        li=[]\n",
    "        def tra(root):\n",
    "            if not root:\n",
    "                return \n",
    "            tra(root.left)\n",
    "            li.append(root.val)\n",
    "            tra(root.right)\n",
    "        print(root)\n",
    "        tra(root)\n",
    "        print('li:',li)\n",
    "        ##### main\n",
    "        self.root=None\n",
    "        \n",
    "        #mid insert:\n",
    "        def midinsert(l,h):\n",
    "            if l>h:\n",
    "                return\n",
    "            \n",
    "            mid=l+h\n",
    "            mid//=2\n",
    "            #print(li,li[mid],l,h)\n",
    "            #root=midinsert(li[mid])\n",
    "            #print(li[mid])\n",
    "            self.li.append(li[mid])\n",
    "            #self.root = insert(self.root,li[mid])\n",
    "            #print('root:',self.root.val)\n",
    "            midinsert(l,mid-1)\n",
    "            midinsert(mid+1,h)\n",
    "            return self.root\n",
    "        self.li=[]\n",
    "        \n",
    "        midinsert(0,len(li)-1)\n",
    "        # 通过了 BUT 有 BUG，现在就是找BUG时间\n",
    "        root=None\n",
    "        #n=len(li)-1\n",
    "        print(self.li)\n",
    "        #n=1\n",
    "        for r in self.li:\n",
    "            root=insert(root,r)\n",
    "            #li=[]\n",
    "            #tra(root)\n",
    "            #print(li)\n",
    "            #if not n :\n",
    "            #    break\n",
    "            #n-=1\n",
    "            #print(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "        # build mid  ，通过中序  直接建立树\n",
    "        ###############################\n",
    "        def build(l,h):\n",
    "            if l>h:\n",
    "                return\n",
    "            mid=l+h\n",
    "            mid//=2\n",
    "            #rt=TreeNode(self.li[mid])\n",
    "            rt=li[mid]\n",
    "            \n",
    "            rt.left=build(l,mid-1)\n",
    "            rt.right=build(mid+1,h)\n",
    "            return rt\n",
    "        return build(0,len(li)-1)\n",
    "\n",
    "\n",
    "        ###############################\n",
    "        def isBst(root):\n",
    "            if not root:\n",
    "                return True,0\n",
    "            l,lh=isBst(root.left)\n",
    "            r,rh=isBst(root.right)\n",
    "            if r and l and abs(lh-rh)<2:\n",
    "                return 1,max(r,l)+1\n",
    "            else:\n",
    "                return 0,root\n",
    "                #这里我们看看 到底是需要返回什么\n",
    "                #以及搜索树的话， 有值我们就可以找到很快的\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        \"\"\"方法2: 迭代\"\"\"\n",
    "        # 中序遍历，将二叉搜索树转为有序数组\n",
    "        nums = self.inOrder(root)\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "            \n",
    "        root = TreeNode(0)  # 初始化根节点\n",
    "        rootQue = [root]  # 队列存放遍历的节点\n",
    "        leftQue = [0]  # 队列存放左区间下标\n",
    "        rightQue = [len(nums) - 1]  # 队列存放右区间下标\n",
    "        \n",
    "        while rootQue:\n",
    "            cur = rootQue.pop(0)\n",
    "            left = leftQue.pop(0)\n",
    "            right = rightQue.pop(0)\n",
    "            \n",
    "            mid = left + (right - left) // 2  # 找到数组中间的元素\n",
    "            cur.val = nums[mid]  # 将中间元素值赋值给节点\n",
    "            \n",
    "            # 处理左区间\n",
    "            if left < mid:\n",
    "                cur.left = TreeNode(0)\n",
    "                rootQue.append(cur.left)\n",
    "                leftQue.append(left)\n",
    "                rightQue.append(mid - 1)\n",
    "            \n",
    "            # 处理右区间\n",
    "            if right > mid:\n",
    "                cur.right = TreeNode(0)\n",
    "                rootQue.append(cur.right)\n",
    "                leftQue.append(mid + 1)\n",
    "                rightQue.append(right)\n",
    "        return root\n",
    "        \n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = []\n",
    "        nums = []\n",
    "        while root or stack:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                nums.append(cur.val)\n",
    "                root = cur.right\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        dic={}\n",
    "        dic=collections.defaultdict(int)\n",
    "        #functions\n",
    "        def getheight(root):\n",
    "            \n",
    "            return max(dic[root.left],dic[root.right])+1\n",
    "        def isavl(root):\n",
    "            return abs(dic[root.left]-dic[root.right])<2\n",
    "        def insert(root,val):\n",
    "            if not root:\n",
    "                #true insert\n",
    "                root=TreeNode(val)\n",
    "                dic[root]=1\n",
    "                #need to update height\n",
    "                #return root\n",
    "            else:\n",
    "                #先insert 完值  然后再判断是否为超过height  这里有个逻辑问题\n",
    "                #对于当前root节点，先查看他是走左边节点还是右边  \n",
    "                #然后要是走左边，判断走左边还是右边 -- LL LR情况 ，如果LR，则给他Insert进去 然后再进行左旋，旋转再右旋：：\n",
    "                #这里使用递归来做 ，问题就出在了这里了。 不管那么多 出来了再检查\n",
    "                if val<root.val:\n",
    "                    root.left=insert(root.left,val)\n",
    "                    if not isavl(root):\n",
    "                        #LR情况    \n",
    "                        if val > root.left.val:\n",
    "                            #leftr first\n",
    "                            root.left=leftr(root.left)\n",
    "                        #LL情况  这里 记住 ，root对应 节点是变的\n",
    "                        root=rightr(root)\n",
    "                elif val >root.val:\n",
    "                    root.right=insert(root.right,val)\n",
    "                    if not isavl(root):\n",
    "                        if val < root.right.val:\n",
    "                            root.right=rightr(root.right)\n",
    "                        root=leftr(root) \n",
    "                else:#same node\n",
    "                    return root\n",
    "            #update height recursively\n",
    "            #在这里更新 需要想的一个问题是 当他们在旋转过程中，切换了root节点的位置时 是否会有冲突 造成影响\n",
    "            dic[root]=getheight(root)\n",
    "            return root\n",
    "\n",
    "                    \n",
    "        #返回的是 旋转后的节点值            \n",
    "        def leftr(root):\n",
    "            right=root.right\n",
    "            root.right=right.left\n",
    "            right.left=root\n",
    "            #update root\n",
    "            #rooth=getheight(root)\n",
    "            dic[root]=getheight(root)\n",
    "            #\n",
    "            dic[right]=getheight(right)\n",
    "            return right\n",
    "        def rightr(root):\n",
    "            left=root.left\n",
    "            root.right=left.right\n",
    "            left.right=root\n",
    "            dic[root]=getheight(root)\n",
    "            dic[left]=getheight(left)\n",
    "            return left\n",
    "        #首先 我们要定义左旋右旋，我差不多也知道\n",
    "        #OK 30分钟 解决手撕AVL的问题好吗 不做完不吃饭\n",
    "        #注意了，首先打好基础： right left | insert |\n",
    "\n",
    "\n",
    "\n",
    "        #################遍历 获取节点\n",
    "        li=[]\n",
    "        def tra(root):\n",
    "            if not root:\n",
    "                return \n",
    "            tra(root.left)\n",
    "            li.append(root.val)\n",
    "            tra(root.right)\n",
    "        print(root)\n",
    "        tra(root)\n",
    "        print('li:',li)\n",
    "        ##### main\n",
    "        self.root=None\n",
    "        \n",
    "        #mid insert:\n",
    "        def midinsert(l,h):\n",
    "            if l>h:\n",
    "                return\n",
    "            mid=l+h\n",
    "            mid//=2\n",
    "            #print(li,li[mid],l,h)\n",
    "            #root=midinsert(li[mid])\n",
    "            self.root = insert(self.root,li[mid])\n",
    "            #print('root:',self.root.val)\n",
    "            midinsert(l,mid-1)\n",
    "            midinsert(mid+1,h)\n",
    "            return self.root\n",
    "        '''midinsert(0,len(li)-1)\n",
    "        return self.root\n",
    "'''\n",
    "\n",
    "        root=None\n",
    "        for r in li:\n",
    "            root=insert(root,r)\n",
    "            #print(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "        # build mid  ，通过中序  直接建立树\n",
    "        ###############################\n",
    "        def build(l,h):\n",
    "            if l>h:\n",
    "                return\n",
    "            mid=l+h\n",
    "            mid//=2\n",
    "            #rt=TreeNode(self.li[mid])\n",
    "            rt=li[mid]\n",
    "            \n",
    "            rt.left=build(l,mid-1)\n",
    "            rt.right=build(mid+1,h)\n",
    "            return rt\n",
    "        return build(0,len(li)-1)\n",
    "\n",
    "\n",
    "        ###############################\n",
    "        def isBst(root):\n",
    "            if not root:\n",
    "                return True,0\n",
    "            l,lh=isBst(root.left)\n",
    "            r,rh=isBst(root.right)\n",
    "            if r and l and abs(lh-rh)<2:\n",
    "                return 1,max(r,l)+1\n",
    "            else:\n",
    "                return 0,root\n",
    "                #这里我们看看 到底是需要返回什么\n",
    "                #以及搜索树的话， 有值我们就可以找到很快的\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = self.traverse(root)\n",
    "        return self.build(nums, 0, len(nums) - 1)\n",
    "\n",
    "    def traverse(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        res += self.traverse(root.left)\n",
    "        res.append(root.val)\n",
    "        res += self.traverse(root.right)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def build(self, nums: List[int], lo: int, hi: int) -> TreeNode:\n",
    "        if lo > hi:\n",
    "            return None\n",
    "        mid = (lo + hi) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "\n",
    "        root.left = self.build(nums, lo, mid - 1)\n",
    "        root.right = self.build(nums, mid + 1, hi)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def __init__(self):\n",
    "    #     self.bp = 0\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 解法1 有序列表+构造\n",
    "        def getInorderList(root):\n",
    "            res = []\n",
    "            stack = []\n",
    "            node = root \n",
    "            while node or stack:\n",
    "                while node:\n",
    "                    stack.append(node)\n",
    "                    node = node.left\n",
    "                node = stack.pop()\n",
    "                res.append(node.val)\n",
    "                node = node.right \n",
    "            return res \n",
    "\n",
    "        def buildAVL(l, r):\n",
    "            mid = (l+r) // 2\n",
    "            while l <= r:\n",
    "                root = TreeNode(res[mid])\n",
    "                root.left = buildAVL(l, mid-1)\n",
    "                root.right = buildAVL(mid+1, r)\n",
    "                return root\n",
    "            else:\n",
    "                return None\n",
    "        \n",
    "        res = getInorderList(root)      \n",
    "        return buildAVL(0, len(res)-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     def balanceBST_node(node):\n",
    "    #         if not root:\n",
    "    #             return root \n",
    "            \n",
    "    #         self.bp = self.treeHeight(root.left) - self.treeHeight(root.right)\n",
    "    #         tmp = node # 暂存\n",
    "    #         tmp_l = node.left\n",
    "    #         tmp_r = node.right\n",
    "\n",
    "    #         if self.bp == 0 or self.bp == 1 or self.bp == -1: # 已经是AVL树了\n",
    "    #             return node \n",
    "    #         elif self.bp > 1:\n",
    "    #             node = node.right\n",
    "    #             if tmp_l:\n",
    "    #                 tmp_l.right = tmp\n",
    "    #                 node.left = tmp_l\n",
    "    #             else:\n",
    "    #                 node.left = tmp \n",
    "    #             balanceBST_node(node)\n",
    "    #         else:\n",
    "    #             node = node.left\n",
    "    #             if tmp_r:\n",
    "    #                 tmp_r.left = tmp \n",
    "    #                 node.right = tmp_r \n",
    "    #             else:\n",
    "    #                 node.right = tmp\n",
    "    #             balanceBST_node(node)\n",
    "    #         return node \n",
    "\n",
    "    #     return balanceBST_node(root)\n",
    "\n",
    "\n",
    "    # def treeHeight(self, node):\n",
    "    #     if not node:\n",
    "    #         return 0\n",
    "        \n",
    "    #     l_height = self.treeHeight(node.left)\n",
    "    #     r_height = self.treeHeight(node.right)\n",
    "    #     return max(l_height, r_height) + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def getInorder(o):\n",
    "            if o.left:\n",
    "                getInorder(o.left)\n",
    "            inorderSeq.append(o.val)\n",
    "            if o.right:\n",
    "                getInorder(o.right)\n",
    "        \n",
    "        def build(l, r):\n",
    "            mid = (l + r) // 2\n",
    "            o = TreeNode(inorderSeq[mid])\n",
    "            if l <= mid - 1:\n",
    "                o.left = build(l, mid - 1)\n",
    "            if mid + 1 <= r:\n",
    "                o.right = build(mid + 1, r)\n",
    "            return o\n",
    "\n",
    "        inorderSeq = list()\n",
    "        #获取中序遍历，二叉搜索树中序是有序的\n",
    "        getInorder(root)\n",
    "        return build(0, len(inorderSeq) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        self.inorder(root, nums)\n",
    "        return self.process(nums, 0, len(nums) - 1)\n",
    "    def inorder(self, root, nums):\n",
    "        if root is None:\n",
    "            return\n",
    "        self.inorder(root.left, nums)\n",
    "        nums.append(root.val)\n",
    "        self.inorder(root.right, nums)\n",
    "    def process(self, nums, left, right):\n",
    "        if left > right:\n",
    "            return \n",
    "        mid = left + (right - left) // 2\n",
    "        midnode = TreeNode(nums[mid])\n",
    "        midnode.left = self.process(nums, left, mid - 1)\n",
    "        midnode.right = self.process(nums, mid + 1, right)\n",
    "        return midnode\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        dp = []\n",
    "        #将二叉搜索树转换为数组\n",
    "        def conversList (cur: TreeNode):\n",
    "            if not cur:\n",
    "                return \n",
    "            conversList(cur.left)\n",
    "            dp.append(cur.val)\n",
    "            conversList(cur.right)\n",
    "        #将数组转化为平衡搜索树\n",
    "        def getResult(nums: List, left, right):\n",
    "            mid = left + (right-left)//2\n",
    "            if right < left:\n",
    "                return\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = getResult(nums, left, mid-1)\n",
    "            root.right = getResult(nums, mid+1, right)\n",
    "            return root\n",
    "        conversList(root)\n",
    "         \n",
    "        return getResult(dp, 0, len(dp)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        rootval=[]\n",
    "\n",
    "        def traversal(root):\n",
    "            nonlocal rootval\n",
    "            if not root:\n",
    "                return \n",
    "            if root.left:\n",
    "                traversal(root.left)\n",
    "            rootval.append(root.val)\n",
    "            if root.right:\n",
    "                traversal(root.right)\n",
    "        \n",
    "        def buildTree(root,start,end):\n",
    "            mid=(start+end)//2\n",
    "            node=TreeNode(root[mid])\n",
    "            if mid>start:\n",
    "                node.left=buildTree(root,start,mid-1)\n",
    "            if mid<end:\n",
    "                node.right=buildTree(root,mid+1,end)\n",
    "            return node\n",
    "        \n",
    "        traversal(root)\n",
    "        return buildTree(rootval,0,len(rootval)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        # 有序树转成有序数组\n",
    "        def traversal(cur):\n",
    "            if not cur: return\n",
    "            traversal(cur.left)\n",
    "            res.append(cur.val)\n",
    "            traversal(cur.right)\n",
    "        # 有序数组转成平衡二叉树\n",
    "        def getTree(nums: List, left, right):\n",
    "            if left > right: return \n",
    "            mid = left + (right -left) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = getTree(nums, left, mid - 1)\n",
    "            root.right = getTree(nums, mid + 1, right)\n",
    "            return root\n",
    "        traversal(root)\n",
    "        return getTree(res, 0, len(res) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def order(self,root,s):\n",
    "        if root==None:\n",
    "            return\n",
    "        self.order(root.left,s)\n",
    "        s.append(root.val)\n",
    "        self.order(root.right,s)\n",
    "    def insert(self,root,val):\n",
    "        if root==None:\n",
    "            return TreeNode(val)\n",
    "        if val<root.val:\n",
    "            root.left=self.insert(root.left,val)\n",
    "        if val>root.val:\n",
    "            root.right=self.insert(root.right,val)\n",
    "        return root\n",
    "    def create(self,s,root):\n",
    "        if s==None:\n",
    "            return root\n",
    "        if len(s)==0:\n",
    "            return root\n",
    "        mid=int(len(s)/2)\n",
    "        root=self.insert(root,s[mid])\n",
    "        root=self.create(s[0:mid],root)\n",
    "        root=self.create(s[mid+1:],root)\n",
    "        return root\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        s=[]\n",
    "        self.order(root,s)\n",
    "        head=None\n",
    "        head=self.create(s,head)\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.traverse(root)\n",
    "        print(self.res)\n",
    "        return self.build(0, len(self.res)-1)\n",
    "\n",
    "    def build(self, l, r):\n",
    "        if l > r:\n",
    "            return\n",
    "        root_index = (l + r) // 2\n",
    "        root = TreeNode(self.res[root_index])\n",
    "        root.left = self.build(l, root_index - 1)\n",
    "        root.right = self.build(root_index + 1, r)\n",
    "        return root\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traverse(root.left)\n",
    "        self.res.append(root.val)\n",
    "        self.traverse(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        # 有序树转成有序数组\n",
    "        def traversal(cur: TreeNode):\n",
    "            if not cur: return\n",
    "            traversal(cur.left)\n",
    "            res.append(cur.val)\n",
    "            traversal(cur.right)\n",
    "        # 有序数组转成平衡二叉树\n",
    "        def getTree(nums: List, left, right):\n",
    "            if left > right: return \n",
    "            mid = left + (right -left) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = getTree(nums, left, mid - 1)\n",
    "            root.right = getTree(nums, mid + 1, right)\n",
    "            return root\n",
    "        traversal(root)\n",
    "        return getTree(res, 0, len(res) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def getNode(node: TreeNode):\n",
    "            nonlocal orderTree\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left:\n",
    "                getNode(node.left)\n",
    "            orderTree.append(node.val)\n",
    "            if node.right:\n",
    "                getNode(node.right)\n",
    "            return\n",
    "        def buildTree(l,r) -> TreeNode:\n",
    "            nonlocal orderTree\n",
    "            mid = (l+r)//2\n",
    "            node = TreeNode(orderTree[mid])\n",
    "            if l <= mid-1:\n",
    "                node.left = buildTree(l,mid-1)\n",
    "            if r >= mid+1:\n",
    "                node.right = buildTree(mid+1,r)\n",
    "            return node\n",
    "        orderTree = []\n",
    "        getNode(root)\n",
    "        return buildTree(0,len(orderTree)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def getInorder(o):\n",
    "            if o.left:\n",
    "                getInorder(o.left)\n",
    "            inorderSeq.append(o.val)\n",
    "            if o.right:\n",
    "                getInorder(o.right)\n",
    "\n",
    "\n",
    "        def build(l,r):\n",
    "            mid=(l+r)//2\n",
    "            o=TreeNode(inorderSeq[mid])\n",
    "            if l<=mid-1:\n",
    "                o.left=build(l,mid-1)\n",
    "            if mid+1<=r:\n",
    "                o.right=build(mid+1,r)\n",
    "            return o\n",
    "\n",
    "        inorderSeq=list()\n",
    "        getInorder(root)\n",
    "        return build(0,len(inorderSeq)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else []\n",
    "\n",
    "\n",
    "    def sortedArrayToBST(self, nums: List[int], left: int, right: int) -> Optional[TreeNode]:\n",
    "        if left > right: return None\n",
    "\n",
    "        mid = (left + right) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums, left, mid - 1)\n",
    "        root.right = self.sortedArrayToBST(nums, mid + 1, right)\n",
    "        return root\n",
    "\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 第二次提交  官方\n",
    "        # 时间复杂度：获得中序遍历的时间代价是 O(n)；\n",
    "        # 建立平衡二叉树的时建立每个点的时间代价为 O(1)，总时间也是 O(n)。故渐进时间复杂度为 O(n)。\n",
    "        # 空间复杂度：这里使用了一个数组作为辅助空间，存放中序遍历后的有序序列，故渐进空间复杂度为 O(n)。\n",
    "        def getInorder(o):\n",
    "            if o.left:\n",
    "                getInorder(o.left)\n",
    "            inorderSeq.append(o.val)\n",
    "            if o.right:\n",
    "                getInorder(o.right)\n",
    "        \n",
    "        def build(l, r):\n",
    "            mid = (l + r) // 2\n",
    "            o = TreeNode(inorderSeq[mid])\n",
    "            if l <= mid - 1:\n",
    "                o.left = build(l, mid - 1)\n",
    "            if mid + 1 <= r:\n",
    "                o.right = build(mid + 1, r)\n",
    "            return o\n",
    "\n",
    "        inorderSeq = list()\n",
    "        getInorder(root)\n",
    "        return build(0, len(inorderSeq) - 1)\n",
    "\n",
    "\n",
    "        # 第一次提交  参考第 108 题\n",
    "        # 先中序遍历转成有序数组，再将有序数组转成平衡二叉搜索树\n",
    "        nums = self.inorderTraversal(root)\n",
    "        return self.sortedArrayToBST(nums, 0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        def search(root):\n",
    "            if root == None:\n",
    "                return []\n",
    "            else:\n",
    "                return search(root.left) + [root.val] + search(root.right)\n",
    "        \n",
    "        def generate(L):\n",
    "            if len(L) == 0:\n",
    "                return None\n",
    "        \n",
    "            k = len(L) // 2\n",
    "            left_tree = generate(L[0:k])\n",
    "            right_tree = generate(L[k+1:])\n",
    "            return TreeNode(L[k], left_tree, right_tree)\n",
    "        \n",
    "        L = search(root)\n",
    "        print(L)\n",
    "        return generate(L)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        inorder=[]\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "            dfs(root.left)\n",
    "            inorder.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "\n",
    "        def build(order):\n",
    "            if len(order)==0:\n",
    "                return None\n",
    "            mid=len(order)//2\n",
    "            root=TreeNode(order[mid])\n",
    "            \n",
    "            left=build(order[:mid])\n",
    "            right=None\n",
    "            if len(order)>mid+1:\n",
    "                right=build(order[mid+1:])\n",
    "            root.left=left\n",
    "            root.right=right\n",
    "            return root\n",
    "        return build(inorder)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return \n",
    "            else:\n",
    "                inorder(root.left)\n",
    "                nums.append(root.val)\n",
    "                inorder(root.right)\n",
    "\n",
    "        def create(nums):\n",
    "            if not nums:\n",
    "                return None\n",
    "            root_idx = len(nums)//2\n",
    "            root = TreeNode(nums[root_idx])\n",
    "            root.left = create(nums[:root_idx])\n",
    "            root.right = create(nums[root_idx+1:])\n",
    "            return root\n",
    "        nums = []\n",
    "        inorder(root)\n",
    "        return create(nums)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else []\n",
    "\n",
    "\n",
    "    def sortedArrayToBST(self, nums: List[int], left: int, right: int) -> Optional[TreeNode]:\n",
    "        if left > right: return None\n",
    "\n",
    "        mid = (left + right) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums, left, mid - 1)\n",
    "        root.right = self.sortedArrayToBST(nums, mid + 1, right)\n",
    "        return root\n",
    "\n",
    "\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 第一次提交  参考第 108 题\n",
    "        # 先中序遍历转成有序数组，再将有序数组转成平衡二叉搜索树\n",
    "        nums = self.inorderTraversal(root)\n",
    "        return self.sortedArrayToBST(nums, 0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 先取出所有值，再选择中间值作为根节点构造二叉树\n",
    "        nodes = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            nodes.append(node.val)\n",
    "        \n",
    "        dfs(root)\n",
    "        \n",
    "        nodes.sort()\n",
    "\n",
    "        # 分治法，每次都选中间值\n",
    "        def add_node(l):\n",
    "            if not l:\n",
    "                return\n",
    "            mid = len(l) >> 1\n",
    "            node = TreeNode(l[mid])\n",
    "            node.left = add_node(l[:mid])\n",
    "            node.right = add_node(l[mid+1:])\n",
    "            return node\n",
    "\n",
    "        \n",
    "        return add_node(nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        vals = []\n",
    "\n",
    "        def DFS(root):\n",
    "            if not root:\n",
    "                return \n",
    "            DFS(root.left)\n",
    "            vals.append(root.val)\n",
    "            DFS(root.right)\n",
    "            return \n",
    "        DFS(root)\n",
    "\n",
    "        def build_tree(lst):\n",
    "            if not lst:\n",
    "                return None\n",
    "            n = len(lst)\n",
    "            if n==1:\n",
    "                return TreeNode(lst[0])\n",
    "            mid = n//2\n",
    "            return TreeNode(lst[mid], build_tree(lst[:mid]),\n",
    "                     build_tree(lst[mid+1:] )   )\n",
    "        \n",
    "        return build_tree(vals)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
